/*
 * Solver.cpp
 *
 *  Created on: 12.10.2010
 *      Author: jilly
 */

#define DEBUG
#define CUT_LEVEL_FACTOR 3

#include <stdio.h>
#include <stdlib.h>
#include <limits>
#include <iostream>
#include <fstream>
#include <stack>
#include "math.h"
#include "mpi/mpi.h"
#include "../objects/BoardException.h"
#include "Solver.h"

//TODO: should be refactored - mpi communication should be moved to another object
using namespace std;

Solver::Solver(Board* board)
{
	this->board = board;
	init();
}

Solver::Solver()
{
	board = NULL;
	init();
}

Solver::~Solver() {
	free(buffer);
	if (jobResponsesAwaiting != NULL) free(jobResponsesAwaiting);
	if (logger != NULL) delete logger;
	delete bestSolution;
}

void Solver::init()
{
	bestSolution = NULL;
	bestMoves = numeric_limits<unsigned int>::max();
	myColor = TOKEN_COLOR_WHITE;
	allocBuffer();
	jobResponsesAwaiting = NULL;
	logger = NULL;
}

void Solver::initLogger(const char* filename)
{
	logger = new Logger(filename);
}

void Solver::allocJobResponsesAwaiting()
{
	if (jobResponsesAwaiting != NULL) free(jobResponsesAwaiting);
	//init job responses awaiting flags
	jobResponsesAwaiting = (bool*) calloc(numberOfProcessors, sizeof(bool));
	for (int i=0; i < numberOfProcessors; i++) jobResponsesAwaiting[i] = false;
}

void Solver::allocBuffer()
{
	bufferSize = BUFFER_INIT_SIZE;
	buffer = (unsigned char*) calloc(bufferSize, sizeof(unsigned char));
}

void Solver::reallocBuffer()
{
	if (buffer != NULL) free(buffer);
	//buffer;
	//set buffer size - we are paranoid so the size of buffer 2 times bigger than necessary :)
	//TODO: check if size is correct
	bufferSize = 2 * (sizeof(Board) + upperBound * sizeof(Node));
	//alloc buffer
	buffer = (unsigned char*) calloc(bufferSize, sizeof(unsigned char));
}

void Solver::sendBufferSizeMessage()
{
	int position = 0, flag = 0;
	MPI_Status status;
	MPI_Request request;
	MPI_Pack(&bufferSize, 1, MPI_INT, buffer, bufferSize, &position, MPI_COMM_WORLD);

	//send bufferSize to other processors - should send only processor 0 !
	for (int i=0, toRank = (myRank + 1) % numberOfProcessors; i < (numberOfProcessors - 1); i++, toRank = (toRank + 1) % numberOfProcessors)
	{
		//send message
		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] I'm going to send buffer size message to [" << toRank << "]" << endl;
		#endif
		MPI_Isend(buffer, position, MPI_PACKED, toRank, MSG_BUFFER_SIZE, MPI_COMM_WORLD, &request);
		do {
			MPI_Test(&request, &flag, &status);
		} while (!flag);
		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] I sent buffer size message to [" << toRank << "]" << endl;
		#endif
	}
}

/**
 * message with new buffer size so that i can realloc my buffer
 * is blocking
 */
void Solver::receiveBufferSizeMessage()
{
	int position = 0;
	MPI_Status status;
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I want to recieve buffer size message" << endl;
	#endif
	MPI_Recv(buffer, bufferSize, MPI_PACKED, MPI_ANY_SOURCE, MSG_BUFFER_SIZE, MPI_COMM_WORLD, &status);
	MPI_Unpack(buffer, bufferSize, &position, &bufferSize, 1, MPI_INT, MPI_COMM_WORLD);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] Buffer size recieved " << bufferSize << endl;
	#endif
}

void Solver::sendSolutionBounds()
{
	int position = 0, flag = 0;
	MPI_Status status;
	MPI_Request request;
	MPI_Pack(&lowerBound, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
	MPI_Pack(&upperBound, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);

	//send bufferSize to other processors - should send only processor 0 !
	for (int i=0, toRank = (myRank + 1) % numberOfProcessors; i < (numberOfProcessors - 1); i++, toRank = (toRank + 1) % numberOfProcessors)
	{
		//send message
		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] I'm going to send solution bounds to [" << toRank << "]" << endl;
		#endif
		MPI_Isend(buffer, position, MPI_PACKED, toRank, MSG_SOLUTION_BOUNDS, MPI_COMM_WORLD, &request);
		do {
			MPI_Test(&request, &flag, &status);
		} while (!flag);
		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] I sent solution bounds to [" << toRank << "]" << endl;
		#endif
	}
}
void Solver::receiveSolutionBounds()
{
	int position = 0;
	MPI_Status status;
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I want to recieve solution bounds message" << endl;
	#endif
	MPI_Recv(buffer, bufferSize, MPI_PACKED, MPI_ANY_SOURCE, MSG_SOLUTION_BOUNDS, MPI_COMM_WORLD, &status);
	MPI_Unpack(buffer, bufferSize, &position, &lowerBound, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
	MPI_Unpack(buffer, bufferSize, &position, &upperBound, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] Recieved solution bounds. min: " << lowerBound << ", max: " << upperBound << endl;
	#endif
}

void Solver::startSolve()
{
	//lowerBound = k
	lowerBound = board->getNumberOfPieces();
	/*
	 * upperBound =	4k 				... n>=k
	 * 				4k - 2(k - n) 	... n < k
	 */
	upperBound =
			(board->getSize() >= board->getNumberOfPieces())
			? (4 * board->getNumberOfPieces())
			: ((4 * board->getNumberOfPieces()) - (2 * (board->getNumberOfPieces() - board->getSize())));

	reallocBuffer();
	//send size of buffer to other processors so that they can realloc
	sendBufferSizeMessage();
	//send solution bounds (min, max) to other processors
	sendSolutionBounds();

	//start solving actual problem
	Node* root = new Node();
	root->setMoves(0);
	root->setMove(NULL);
	root->setParent(NULL);
	root->setState(STATE_FRESH);

	board->printBoard();
	logger->getLogger() << "[" << myRank << "] Min moves:	" << lowerBound << endl;
	logger->getLogger() << "[" << myRank << "] Max moves:	" << upperBound << endl << endl;

	//first try queen
	doSolve(root, MOVE_QUEEN);
	if (bestMoves > lowerBound)
	{
		//then try bishop
		doSolve(root, MOVE_BISHOP);
	}
	delete root;
}

void Solver::doSolve(Node * root, int whoStarts)
{
	allocJobResponsesAwaiting(); //for processing jobs

	stack<Node*> stack;

	if (myRank == 0)
	{
		logger->getLogger() << "[" << myRank << "] Solving ..." << endl;
		logger->getLogger() << "[" << myRank << "] Starts:		" << ((whoStarts == MOVE_QUEEN) ? "Queen" : "Bishop") << endl;

		/**
		 * don't push root on stack
		 * instead push all children of root to stack
		 */
		/**
		 * if bishop can't move - will quit because stack is empty ...
		 * example: (bishop is in corner blocked by queen)
		 * 		B.
		 * 		.Q
		 */
		list<Move*> possibleMoves = ((whoStarts == MOVE_QUEEN) ? board->getQueenPossibleMoves() : board->getBishopPossibleMoves());
		for (list<Move*>::iterator it = possibleMoves.begin(); it != possibleMoves.end(); it++)
		{
			Node* child = new Node();
			Move* move = (*it);
			child->setMove(move);
			child->setParent(root);
			child->setMoves(root->getMoves() + 1);
			child->setState(STATE_FRESH);
			child->setMovesWithoutHit(board->isPieceOnPosition(move->getToX(), move->getToY()) ? 0 : 1);
			stack.push(child);
		}
		possibleMoves.clear();
	} //END myRank == 0

	unsigned long counter = 0;
	unsigned long statesCounter = 0;
	idle = false;
	receivedToken = false;
	workDone = false;
	foundBestSolution = false;
	//set next computer to ask for job to my right neighbor
	jobRequestToRank = (myRank + 1) % numberOfProcessors;

	while (!workDone)
	{
		counter++;
		if ((counter % CHECK_MSG_AMOUNT) == 0)
		{
			//check if there are any messages from other processors
			//if so, process them
			communicate(stack);
		}
		else
		{
			//processor 0 received best possible solution => quit
			if (foundBestSolution && myRank == 0) {
				clearStack(stack);
				break;
			}
			if (stack.empty())
			{
				//processor 0 will quit computation
				if (myRank == 0) break;
				else
				{
					//for processors 1 .. n-1: go to idle state
					if (!idle)
					{
						idle = true;
						#ifdef DEBUG
						logger->getLogger() << "[" << myRank << "] I am now idle" << endl;
						#endif
					}
				}
			}
			else //stack not empty
			{
				statesCounter++;
				doStep(stack);
			}
		}
	} //while true

	//processor 0 is responsible for termination of computation
	if (myRank == 0)
	{
		myColor = TOKEN_COLOR_WHITE;
		terminationDone = false;
		int finishCounter = 0;
		bool tokenSent = false;
		receivedToken = false;
		while (!terminationDone)
		{
			finishCounter++;
			if ((finishCounter % CHECK_MSG_AMOUNT) == 0)
			{
				communicate(stack);
			}
			else //active waiting ... :(
			{
				if (receivedToken && !terminationDone)
				{
					receivedToken = false;
					tokenSent = true;
					sendToken();
				}
				if (!tokenSent)
				{
					tokenSent = true;
					receivedToken = false;
					sendToken();
				}
			}
			//terminate computation
		}

		//we can safely terminate
		sendFinish();
		counter += finishCounter;
	}

	//TODO: check
	clearStack(stack);

	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] Visited states:	" << statesCounter << endl;
	logger->getLogger() << "[" << myRank << "] Loops: " << counter << endl;
	logger->getLogger() << "[" << myRank << "] Finished solving" << endl << endl;
	#endif

	MPI_Barrier(MPI_COMM_WORLD);
}

template <typename T>
void Solver::printStack(T &stackRef)
{
	stack<Node*> tmpStack;

	int counter = 0;
	while (!stackRef.empty())
	{
		Node* node = stackRef.top();
		Move* itsMove = node->getMove();
		logger->getLogger() << "(" << counter << ") who: " << ((itsMove->getWho() == MOVE_QUEEN) ? "queen" : "bishop") << ", move: [" <<
				itsMove->getFromX() << "," << itsMove->getFromY() << "] -> [" << itsMove->getToX() << "," << itsMove->getToY() << "], "
				<< "moves: " << node->getMoves() << ", state: " << node->getState() << endl;
		stackRef.pop();
		tmpStack.push(node);
		counter++;
	}
	logger->getLogger() << endl << endl;

	while (!tmpStack.empty())
	{
		stackRef.push(tmpStack.top());
		tmpStack.pop();
	}
}

template <typename T>
void Solver::trySendWork(T &stackRef, int toRank)
{
	stack<Node*> tmpStack;

	/**
	 * maximum node's moves to be selected
	 */
	unsigned int cutLevel = (bestMoves > upperBound)
		? (int) floor((upperBound - lowerBound) / CUT_LEVEL_FACTOR)
		: (int) floor(bestMoves / CUT_LEVEL_FACTOR);


	Node* workNode = NULL;
	/**
	 * thats pretty crazy!!
	 * traverse stack and try to find node to send
	 * during traversing we remove nodes from out local stack
	 * and if nodes are in OPEN_STATE we perform moves backwards on
	 * board, so that we can send correct board object to
	 * another processor
	 *
	 * afterwards, we must revert back to state from
	 * which we started finding node to send, therefore perform
	 * moves forward
	 */

//FIXME: debug
//	#ifdef DEBUG
//	logger->getLogger() << "[" << myRank << "] BOARD BEFORE WORK SEARCH" << endl;
//	board->printBoard();
//	#endif

	while (true)
	{
		if (stackRef.empty()) break;

		Node* node = stackRef.top();

		if (node->getState() == STATE_FRESH)
		{
			if (node->getMoves() <= cutLevel)
			{
				workNode = node;
				break;
			}
		}
		else if (node->getState() == STATE_OPEN)
		{
//FIXME: debug
//			#ifdef DEBUG
//			Move* move = node->getMove();
//			logger->getLogger() << "Performing move back [" << move->getToX() << "," << move->getToY() << "] -> ["
//					<< move->getFromX() << "," << move->getFromY() << "] by "
//					<< ((move->getWho() == MOVE_QUEEN) ? "QUEEN" : "BISHOP") << endl;
//			#endif
			performMoveBack(node->getMove());
//FIXME: debug
//			#ifdef DEBUG
//			board->printBoard();
//			#endif
		}

		stackRef.pop();
		tmpStack.push(node);
	}

	if (workNode != NULL)
	{
		//send WORK_SENT
		int position = 0;

		int nodesSent = workNode->getMoves();
		MPI_Pack(&nodesSent, 1, MPI_INT, buffer, bufferSize, &position, MPI_COMM_WORLD);
		//serialize nodes on (future) stack
		Node* packedNode = workNode;
		for (int i=0; i < nodesSent; i++)
		{
			Move* itsMove = packedNode->getMove();
			int who = itsMove->getWho();
			unsigned int fromX = itsMove->getFromX();
			unsigned int fromY = itsMove->getFromY();
			unsigned int toX = itsMove->getToX();
			unsigned int toY = itsMove->getToY();
			bool wasHit = itsMove->wasHit();
			unsigned int moves = packedNode->getMoves();
			unsigned int movesWithoutHit = packedNode->getMovesWithoutHit();
			unsigned short state = packedNode->getState();

			MPI_Pack(&who, 1, MPI_INT, buffer, bufferSize, &position, MPI_COMM_WORLD);
			MPI_Pack(&fromX, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
			MPI_Pack(&fromY, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
			MPI_Pack(&toX, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
			MPI_Pack(&toY, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
			MPI_Pack(&wasHit, 1, MPI_BYTE, buffer, bufferSize, &position, MPI_COMM_WORLD);
			MPI_Pack(&moves, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
			MPI_Pack(&movesWithoutHit, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
			MPI_Pack(&state, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);

			packedNode = packedNode->getParent();
		}

		//serialize board
		unsigned int size = board->getSize();
		bool** boardArray = board->getBoard();
		MPI_Pack(&size, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
		for (unsigned int y=0; y < size; y++)
		{
			for (unsigned int x=0; x < size; x++)
			{
				MPI_Pack(&boardArray[x][y], 1, MPI_BYTE, buffer, bufferSize, &position, MPI_COMM_WORLD);
			}
		}
		Piece* bishopPiece = board->getBishop();
		Piece* queenPiece = board->getQueen();

		unsigned int bishopX = bishopPiece->getX();
		unsigned int bishopY = bishopPiece->getY();
		unsigned int queenX = queenPiece->getX();
		unsigned int queenY = queenPiece->getY();

		//finally pack queen's a bishop's position
		MPI_Pack(&queenX, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
		MPI_Pack(&queenY, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
		MPI_Pack(&bishopX, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
		MPI_Pack(&bishopY, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);


		//now send message ...
		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] I'm going to send WORK_SENT to [" << toRank << "]" << endl;
		#endif

		//NOTE: for correct termination we must set our color to black if its necessary
		if (toRank < myRank) myColor = TOKEN_COLOR_BLACK;
		//send message
		int flag = 0;
		MPI_Status status;
		MPI_Request request;
		MPI_Isend(buffer, position, MPI_PACKED, toRank, MSG_WORK_SENT, MPI_COMM_WORLD, &request);
		do {
			MPI_Test(&request, &flag, &status);
		} while (!flag);
		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] I sent WORK_SENT to [" << toRank << "]" << endl;
		#endif

		/**
		 * IMPORTANT!!!
		 * set state of sent node to ZOMBIE
		 * can't set its state to OPEN so that we just won't expand it
		 * but we must set its state to ZOMBIE because OPEN nodes
		 * are nodes that were locally visited and we perform
		 * performMoveBack() on each of them
		 */
		workNode->setState(STATE_ZOMBIE);
	}
	else
	{
		//send WORK_NOWORK
		sendNoWork(toRank);
	}

	/**
	 * here we must revert state so that we can continue computation
	 * push pack all nodes from 'tmpStack' to 'stackRef'
	 * and perform moves forward
	 */
//FIXME: debug
//	#ifdef DEBUG
//	logger->getLogger() << "Now reverting to previous position" << endl;
//	board->printBoard();
//	#endif
	while (!tmpStack.empty())
	{
		Node* node = tmpStack.top();
		stackRef.push(node);
		if (node->getState() == STATE_OPEN)
		{

//FIXME: debug
//			#ifdef DEBUG
//			Move* move = node->getMove();
//			logger->getLogger() << "Performing move forward [" << move->getFromX() << "," << move->getFromY() << "] -> ["
//					<< move->getToX() << "," << move->getToY() << "] by "
//					<< ((move->getWho() == MOVE_QUEEN) ? "QUEEN" : "BISHOP") << endl;
//
//			#endif
			performMove(node->getMove());
//FIXME: debug
//			#ifdef DEBUG
//			board->printBoard();
//			#endif
		}
		tmpStack.pop();
	}

//FIXME: debug
//	#ifdef DEBUG
//	logger->getLogger() << "[" << myRank << "] BOARD AFTER WORK SEARCH" << endl;
//	board->printBoard();
//	#endif
}

template <typename T>
void Solver::receiveWork(T &stackRef)
{
	MPI_Status status;
	int position = 0;
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I want to receive work" << endl;
	#endif
	MPI_Recv(buffer, bufferSize, MPI_PACKED, MPI_ANY_SOURCE, MSG_WORK_SENT, MPI_COMM_WORLD, &status);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] Received work message" << endl;
	#endif

	int nodesSent;
	MPI_Unpack(buffer, bufferSize, &position, &nodesSent, 1, MPI_INT, MPI_COMM_WORLD);

	stack<Node*> tmpStack;
	//unpack nodes
	Node* prevNode = NULL; //for parent assignment
	for (int i=0; i < nodesSent; i++)
	{
		//first Move object
		Move* move;
		int who;
		unsigned int fromX, fromY, toX, toY;
		bool wasHit;

		MPI_Unpack(buffer, bufferSize, &position, &who, 1, MPI_INT, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &fromX, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &fromY, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &toX, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &toY, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &wasHit, 1, MPI_BYTE, MPI_COMM_WORLD);

		move = new Move(who, fromX, fromY, toX, toY);
		move->setHit(wasHit);

		//then Node object
		Node* node;
		unsigned int moves, movesWithoutHit;
		unsigned short state;
		MPI_Unpack(buffer, bufferSize, &position, &moves, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &movesWithoutHit, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &state, 1, MPI_UNSIGNED, MPI_COMM_WORLD);

		node = new Node();
		node->setMove(move);
		node->setMoves(moves);
		node->setMovesWithoutHit(movesWithoutHit);
		node->setState(state);

		/**
		 * parent node assignment
		 * nodes are sent from child to parent,
		 * therefore assign parent when it is deserialized
		 */
		if (prevNode != NULL) prevNode->setParent(node);
		prevNode = node;

		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] Got NODE. state: " << ((state == STATE_FRESH) ? "fresh" : "open")
				<< ", who: " << ((who == MOVE_QUEEN) ? "queen" : "bishop")
				<< ", [" << fromX << "," << fromY << "] -> [" << toX << "," << toY << "], wasHit: " << ((wasHit) ? "true" : "false")
				<< ", moves: " << moves << endl;
		#endif
		/**
		 * push nodes to tmpStack
		 * we must revert order of nodes and then
		 * push all of them to stack
		 */
		tmpStack.push(node);
	}

	/**
	 * we didn't receive root, but we must set parent to fake root node
	 * for first parent on stack
	 */
	//TODO: check

	Node* root = new Node();
	root->setMoves(0);
	root->setMove(NULL);
	root->setParent(NULL);
	root->setState(STATE_OPEN); //this should never be checked but we are paranoid

	tmpStack.top()->setParent(root);

	//clear stack
	while (!stackRef.empty())
	{
		Node* toDelete = stackRef.top();
		stackRef.pop();
		delete toDelete;
	}

	//push all nodes to my local stack
	while (!tmpStack.empty())
	{
		stackRef.push(tmpStack.top());
		tmpStack.pop();
	}

	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] Now my stack size is: " << stackRef.size() << endl;
	#endif

	//now deserialize Board object
	unsigned int boardSize;
	MPI_Unpack(buffer, bufferSize, &position, &boardSize, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
	Board* newBoard = new Board(boardSize);
	for (unsigned int y=0; y < boardSize; y++)
	{
		for (unsigned int x=0; x < boardSize; x++)
		{
			bool isPiece;
			MPI_Unpack(buffer, bufferSize, &position, &isPiece, 1, MPI_BYTE, MPI_COMM_WORLD);
			if (isPiece)
			{
				#ifdef DEBUG
				logger->getLogger() << "[" << myRank << "] NEWBOARD Placing piece to [" << x << "," << y << "]" << endl;
				#endif

//				#ifdef DEBUG
//				try {
//				#endif
					newBoard->addPiece(x, y);
//				#ifdef DEBUG
//				}
//				catch (const BoardException& e)
//				{
//					logger->getLogger() << "[" << myRank << "] EXCEPTION: (receiveWork)" << e.what() << endl;
//				}
//				#endif
			}
		}
	}

	//read positions of queen and bishop
	unsigned int bishopX, bishopY, queenX, queenY;
	MPI_Unpack(buffer, bufferSize, &position, &queenX, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
	MPI_Unpack(buffer, bufferSize, &position, &queenY, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
	MPI_Unpack(buffer, bufferSize, &position, &bishopX, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
	MPI_Unpack(buffer, bufferSize, &position, &bishopY, 1, MPI_UNSIGNED, MPI_COMM_WORLD);

	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] NEWBOARD Placing queen to [" << queenX << "," << queenY << "]" << endl;
	#endif
	newBoard->placeQueen(queenX, queenY);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] NEWBOARD Placing bishop to [" << bishopX << "," << bishopY << "]" << endl;
	#endif
	newBoard->placeBishop(bishopX, bishopY);

	if (board != NULL) delete board;
	board = newBoard;
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] My NEWBOARD is" << endl;
	board->writeBoard(logger->getLogger());
	#endif
	idle = false;
	jobResponsesAwaiting[status.MPI_SOURCE] = false;
}

void Solver::sendNoWork(int toRank)
{
	int position = 0, flag = 0;
	MPI_Status status;
	MPI_Request request;
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I'm going to send NOWORK to [" << toRank << "]" << endl;
	#endif
	MPI_Isend(buffer, position, MPI_PACKED, toRank, MSG_WORK_NOWORK, MPI_COMM_WORLD, &request);
	do {
		MPI_Test(&request, &flag, &status);
	} while (!flag);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I sent NOWORK to [" << toRank << "]" << endl;
	#endif
}

void Solver::sendToken()
{
	int position = 0, flag = 0;
	MPI_Status status;
	MPI_Request request;
	int toRank = (myRank + 1) % numberOfProcessors;
	MPI_Pack(&myColor, 1, MPI_INT, buffer, bufferSize, &position, MPI_COMM_WORLD);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I'm going to send token (" << myColor << ") to [" << toRank << "]" << endl;
	#endif
	MPI_Isend(buffer, position, MPI_PACKED, toRank, MSG_END_TOKEN, MPI_COMM_WORLD, &request);
	do {
		MPI_Test(&request, &flag, &status);
	} while (!flag);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I sent token (" << myColor << ") to [" << toRank << "]" << endl;
	#endif
}
void Solver::receiveToken()
{
	MPI_Status status;
	int tokenColor, position = 0;
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I want to receive token" << endl;
	#endif
	MPI_Recv(buffer, bufferSize, MPI_PACKED, MPI_ANY_SOURCE, MSG_END_TOKEN, MPI_COMM_WORLD, &status);
	MPI_Unpack(buffer, bufferSize, &position, &tokenColor, 1, MPI_INT, MPI_COMM_WORLD);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I received token (" << tokenColor << ") from [" << status.MPI_SOURCE << "]" << endl;
	#endif
	receivedToken = true;
	if (myRank == 0 && tokenColor == TOKEN_COLOR_WHITE) terminationDone = true;
}

template <typename T>
void Solver::doStep(T &stackRef)
{
	Node* node = stackRef.top();
	//first check node's state
	switch(node->getState())
	{
		case STATE_FRESH:
			/**
			 * for fresh nodes (visited for the first time)
			 * we perform move and try to expand it if its not a solution
			 */

			//change node's state to OPEN (it has been visited)
			node->setState(STATE_OPEN);

			/**
			 * move either queen or bishop to position and set if this move hits / conquers
			 * piece (for backtrack - reconstruction of previous configuration
			 * of board)
			 */
			performMove(node->getMove());

			if (skipNode(node)) return;

			if (board->getNumberOfPieces() != 0)
			{
				expandNode(node, stackRef);
			}
			else
			{
				//we found solution
				#ifdef DEBUG
				logger->getLogger() << "[" << myRank << "] Found solution:	" << node->getMoves() << " moves" << endl;
				#endif

				if (bestSolution != NULL) delete bestSolution;
				bestMoves = node->getMoves();
				bestSolution = createSolution(node);

				//TODO: mpi check
				sendSolution(bestSolution);
				if (bestMoves == lowerBound)
				{
					/**
					 * may quit computation now, found best solution for problem
					 * but we must clear stack and memory !!!
					 */
					#ifdef DEBUG
					logger->getLogger() << "[" << myRank << "] I found best solution" << endl;
					#endif
					clearStack(stackRef);
					#ifdef DEBUG
					logger->getLogger() << "[" << myRank << "] My stack size is now: " << stackRef.size() <<  " (empty: " << stackRef.empty() << ")" << endl;
					#endif
					foundBestSolution = true;
				}
				return;
			}
			break; //FRESH node

		case STATE_OPEN:
		case STATE_ZOMBIE:
			/**
			 * here we revisit node (after subtree of all posibble movements from
			 * this node was tried) -> backtracking
			 */
			//remove open node from stack
			stackRef.pop();
			//perform move back (either queen or bishop)
			if (node->getState() == STATE_OPEN) performMoveBack(node->getMove());
			//finally delete node
			delete node;
			break; //OPEN node
	} //switch state
}

template <typename T>
void Solver::communicate(T &stack)
{
	int flag;
	MPI_Status status;
//	#ifdef DEBUG
//	logger->getLogger() << "[" << myRank << "] Checking messages" << endl;
//	#endif

	while (true)
	{
		MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);
		if (!flag) break;
		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] Got message with tag ";
		switch(status.MPI_TAG)
		{
			case 1000: logger->getLogger() << "MSG_WORK_REQUEST"; break;
			case 1001: logger->getLogger() << "MSG_WORK_SENT"; break;
			case 1002: logger->getLogger() << "MSG_WORK_NOWORK"; break;
			case 1003: logger->getLogger() << "MSG_END_TOKEN"; break;
			case 1004: logger->getLogger() << "MSG_FINISH"; break;
			case 1005: logger->getLogger() << "MSG_SOLUTION"; break;
			case 1007: logger->getLogger() << "MSG_BUFFER_SIZE"; break;
			case 1008: logger->getLogger() << "MSG_SOLUTION_BOUNDS"; break;
			default: logger->getLogger() << "!!!UNKNOWN!!!";
		}
		logger->getLogger() << endl;
		#endif
		switch(status.MPI_TAG)
		{
			case MSG_WORK_REQUEST:
				receiveWorkRequest();
				if (!receivedToken)
					trySendWork(stack, status.MPI_SOURCE);
				else
					sendNoWork(status.MPI_SOURCE);
				break;
			case MSG_WORK_SENT:
				receiveWork(stack);
				nextNeighborForWork();
				break;
			case MSG_WORK_NOWORK:
				receiveNoWork();
				nextNeighborForWork();
				break;
			case MSG_END_TOKEN:
				receiveToken();
				break;
			case MSG_FINISH:
				receiveFinish();
				workDone = true;
				break;
			case MSG_SOLUTION:
				//TODO: mpi check
				#ifdef DEBUG
				logger->getLogger() << "[" << myRank << "] BEST MOVES BEFORE:" << bestMoves << endl;
				#endif
				receiveSolution();
				#ifdef DEBUG
				logger->getLogger() << "[" << myRank << "] BEST MOVES AFTER:" << bestMoves << endl;
				#endif
				break;
		}
	}

	//TODO: check
	if (idle && myRank != 0)
	{
		//don't ask for another job, i already received token
		if (receivedToken)
		{
			receivedToken = false;
			sendToken();
			myColor = TOKEN_COLOR_WHITE;
		}
		else //not received end token yet
		{
			//if i'm not waiting for response
			if (!jobResponsesAwaiting[jobRequestToRank] && !foundBestSolution)
			{
				#ifdef DEBUG
				logger->getLogger() << "[" << myRank << "] I have nothing to do - sending work request" << endl;
				#endif
				sendWorkRequest();
			}
		}

	}

}

void Solver::nextNeighborForWork()
{
	//will loop once, or twice
	do
	{
		jobRequestToRank += 1;
		jobRequestToRank %= numberOfProcessors;
	} while (jobRequestToRank == myRank);
}

void Solver::receiveWorkRequest()
{
	MPI_Status status;
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I want to receive WORK_REQUEST" << endl;
	#endif
	MPI_Recv(buffer, bufferSize, MPI_PACKED, MPI_ANY_SOURCE, MSG_WORK_REQUEST, MPI_COMM_WORLD, &status);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I received WORK_REQUEST from [" << status.MPI_SOURCE << "]" << endl;
	#endif
}

void Solver::sendFinish()
{
	int position = 0, flag = 0;
	MPI_Request request;
	MPI_Status status;

	//send bufferSize to other processors - should send only processor 0 !
	for (int i=0, toRank = (myRank + 1) % numberOfProcessors; i < (numberOfProcessors - 1); i++, toRank = (toRank + 1) % numberOfProcessors)
	{
		//send message
		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] I'm going to send FINISH to [" << toRank << "]" << endl;
		#endif
		MPI_Isend(buffer, position, MPI_PACKED, toRank, MSG_FINISH, MPI_COMM_WORLD, &request);
		do {
			MPI_Test(&request, &flag, &status);
		} while (!flag);
		#ifdef DEBUG
		logger->getLogger() << "[" << myRank << "] I sent FINISH to [" << toRank << "]" << endl;
		#endif
	}
}

void Solver::receiveFinish()
{
	MPI_Status status;
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I want to receive FINISH" << endl;
	#endif
	MPI_Recv(buffer, bufferSize, MPI_PACKED, MPI_ANY_SOURCE, MSG_FINISH, MPI_COMM_WORLD, &status);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I received FINISH from [" << status.MPI_SOURCE << "]" << endl;
	#endif
}

void Solver::receiveNoWork()
{
	MPI_Status status;
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I want to receive NOWORK" << endl;
	#endif
	MPI_Recv(buffer, bufferSize, MPI_PACKED, MPI_ANY_SOURCE, MSG_WORK_NOWORK, MPI_COMM_WORLD, &status);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I received NOWORK from [" << status.MPI_SOURCE << "]" << endl;
	#endif
	jobResponsesAwaiting[status.MPI_SOURCE] = false;
}

void Solver::receiveSolution()
{
	MPI_Status status;
	int position=0, who;
	unsigned int numberOfMoves;
	unsigned int fromX, fromY, toX, toY;

    MPI_Recv(buffer, bufferSize, MPI_PACKED, MPI_ANY_SOURCE, MSG_SOLUTION, MPI_COMM_WORLD, &status);

	MPI_Unpack(buffer, bufferSize, &position, &numberOfMoves, 1, MPI_UNSIGNED, MPI_COMM_WORLD);


	#ifdef DEBUG
    logger->getLogger() << "[" << myRank << "] RECEIVED solution with " << numberOfMoves << " moves [mine is " << bestMoves << " moves] "
    	<< "[source: " << status.MPI_SOURCE << "]" << endl;
	#endif

	//my local solution is better
	if (numberOfMoves >= bestMoves)
	{
		return;
	}

	Solution* solution = new Solution();

	//read solution moves
	for (unsigned int i=0; i < numberOfMoves; i++)
	{
		MPI_Unpack(buffer, bufferSize, &position, &who, 1, MPI_INT, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &fromX, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &fromY, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &toX, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		MPI_Unpack(buffer, bufferSize, &position, &toY, 1, MPI_UNSIGNED, MPI_COMM_WORLD);
		Move* move = new Move(who, fromX, fromY, toX, toY);
		solution->addNextMove(move);
	}

	if (bestSolution != NULL) delete bestSolution;
	bestSolution = solution;
	bestMoves = numberOfMoves;
	if (bestMoves == lowerBound) foundBestSolution = true;
}

void Solver::sendSolution(Solution* solution)
{
	list<Move*> moves = solution->getMoves();
	unsigned int numberOfMoves = moves.size();
	int position = 0, flag = 0;
	MPI_Status status;
	MPI_Request request;

	//how many moves are we sending so that reciever knows how many moves should unpack
	MPI_Pack(&numberOfMoves, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);

	//now pack each move in list
	for (list<Move*>::iterator it = moves.begin(); it != moves.end(); it++)
	{
		Move* move = (*it);
		int who = move->getWho();
		unsigned int fromX = move->getFromX();
		unsigned int toX = move->getToX();
		unsigned int fromY = move->getFromY();
		unsigned int toY = move->getToY();

		MPI_Pack(&who, 1, MPI_INT, buffer, bufferSize, &position, MPI_COMM_WORLD);
		MPI_Pack(&fromX, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
		MPI_Pack(&fromY, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
		MPI_Pack(&toX, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
		MPI_Pack(&toY, 1, MPI_UNSIGNED, buffer, bufferSize, &position, MPI_COMM_WORLD);
		//TODO: maybe pack also hit ???
	}

	//send solution to other processors
	for (int i=0, toRank = (myRank + 1) % numberOfProcessors; i < (numberOfProcessors - 1); i++, toRank = (toRank + 1) % numberOfProcessors)
	{
		//send message
		//TODO: use Isend ???
		#ifdef DEBUG
		 logger->getLogger() << "[" << myRank << "] SENDING solution with " << numberOfMoves << " moves to [" << toRank << "]" << endl;
		#endif
		MPI_Isend(buffer, position, MPI_PACKED, toRank, MSG_SOLUTION, MPI_COMM_WORLD, &request);
		do {
			MPI_Test(&request, &flag, &status);
		} while (!flag);
		#ifdef DEBUG
		 logger->getLogger() << "[" << myRank << "] SENT solution with " << numberOfMoves << " moves to [" << toRank << "]" << endl;
		#endif
	}
}

void Solver::sendWorkRequest()
{
	int position = 0, flag = 0;
	int data = 0; //no data
	MPI_Status status;
	MPI_Request request;
	jobResponsesAwaiting[jobRequestToRank] = true;
	MPI_Pack(&data, 1, MPI_INT, buffer, bufferSize, &position, MPI_COMM_WORLD);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] I will send job request to [" << jobRequestToRank << "]" << endl;
	#endif
	MPI_Isend(buffer, position, MPI_PACKED, jobRequestToRank, MSG_WORK_REQUEST, MPI_COMM_WORLD, &request);
	do {
		MPI_Test(&request, &flag, &status);
	} while (!flag);
	#ifdef DEBUG
	logger->getLogger() << "[" << myRank << "] SENT job request to [" << jobRequestToRank << "]" << endl;
	#endif
}

bool Solver::skipNode(Node* node)
{
	/**
	 * pruning tree
	 * don't expand nodes which are useless
	 * useless nodes are:
	 * 		- nodes where number of moves is bigger that upper bound of moves for
	 * 			this problem
	 * 		- nodes that have more moves that current best solution
	 * 		- nodes from which we have to do amount of moves such that this
	 * 		  solution would be worse that current best solution or won't
	 * 		  be within bounds (would be more moves than upperBound)
	 */
	if 	(
			node->getMoves() > upperBound //out of bounds
			|| (node->getMoves() >= bestMoves) //worse than currently best solution
			|| (
				/*
				 * we yet found some solution, expanding this node is useless because
				 * minimal number of moves to eliminate remaining pieces on board
				 * plus yet done moves is bigger than currently best solution
				 */
					bestSolution != NULL
					&& ((bestMoves - node->getMoves()) < board->getNumberOfPieces())
			)
		)
		//don't delete node here !!!
	{
		return true;
	}
	return false;
}

template <typename T>
void Solver::clearStack(T &stack)
{
	while (!stack.empty())
	{
		Node* node = stack.top();
		//must revert state of board to the begining
		//therefore revert changes made by yet visited nodes
		if (node->getState() == STATE_OPEN)
		{
			performMoveBack(node->getMove());
		}
		stack.pop();
		delete node;
	}
}

template <typename T>
void Solver::expandNode(Node* node, T &stack)
{
	list<Move*> possibleMoves = (node->getMove()->getWho() == MOVE_QUEEN)
			? board->getBishopPossibleMoves()
			: board->getQueenPossibleMoves();

	//push nodes children on stack
	for (list<Move*>::iterator it = possibleMoves.begin(); it != possibleMoves.end(); it++)
	{
		Move* m = (*it);
		//limit also expanded nodes
		//counts how many moves without hit will be after doing this move
		bool willBeHit = board->isPieceOnPosition(m->getToX(), m->getToY());
		unsigned int numberOfPieces = (willBeHit) ? board->getNumberOfPieces() - 1 : board->getNumberOfPieces();
		unsigned int movesWithoutHit =
			willBeHit
			? 0
			: node->getMovesWithoutHit() + 1;
		unsigned int moves = node->getMoves() + 1;

		if
		(
				movesWithoutHit >= 4 //we must conquer in every 4th move
				|| moves == bestMoves
				||
				(
					bestSolution != NULL
					&& ((bestMoves - moves) < numberOfPieces)
				)
		)
		{
			delete m;
			continue;
		}

		Node* child = new Node();
		child->setMove(m);
		child->setParent(node);
		child->setMoves(node->getMoves() + 1);
		child->setState(STATE_FRESH);
		child->setMovesWithoutHit(movesWithoutHit);
		stack.push(child);
	}
	possibleMoves.clear();
}

void Solver::performMove(Move *move)
{
	if (move->getWho() == MOVE_QUEEN)
		move->setHit(board->moveQueen(move->getToX(), move->getToY()));
	else
		move->setHit(board->moveBishop(move->getToX(), move->getToY()));
}

void Solver::performMoveBack(Move* move)
{
	if (move->getWho() == MOVE_QUEEN)
		board->moveQueen(move->getFromX(), move->getFromY());
	else
		board->moveBishop(move->getFromX(), move->getFromY());
	/**
	 * add piece back on board if this move conquered piece
	 */
	if (move->wasHit())
	{
		#ifdef DEBUG
//		logger->getLogger() << "[" << myRank << "] Placing piece back to [" << move->getToX() << "," << move->getToY() << "]" << endl;
		#endif

//		#ifdef DEBUG
//		try {
//		#endif
		board->addPiece(move->getToX(), move->getToY());
//		#ifdef DEBUG
//		}
//		catch (const BoardException& e)
//		{
//			logger->getLogger() << "[" << myRank << "] EXCEPTION: (performMoveBack())" << e.what() << endl;
//		}
//		#endif
	}
}

Solution* Solver::createSolution(Node* lastNode)
{
//FIXME: debug
//	#ifdef DEBUG
//	logger->getLogger() << "[" << myRank << "] Creating solution (reversed output - source .. root)" << endl;
//	#endif
	Solution* s = new Solution();
	Node* n = lastNode;
	#ifdef DEBUG
	int count = 0;
	#endif
	do {
		#ifdef DEBUG
		count++;
		#endif
		Move* m = n->getMove();
//FIXME: debug
//		#ifdef DEBUG
//		logger->getLogger() << "[" << myRank << "] Adding move " << count << endl;
//		m->print();
//		#endif
		s->addPrevMove(m->clone());
		n = n->getParent();
	} while (n->getParent() != NULL);
	return s;
}

void Solver::writeSolution(ofstream& stream)
{
	if (bestSolution == NULL)
	{
		stream << "ERROR: No solution found!" << endl;
		return;
	}

	stream << "----------------" << endl
		 << "  BEST SOLUTION " << endl
		 << "----------------" << endl;

	list<Move*> moves = bestSolution->getMoves();

	stream << "# of moves:	" << moves.size() << endl << endl;
	stream << "Initial state" << endl << endl;

	board->writeBoard(stream);

	int moveNumber = 1;
	for (list<Move*>::iterator it = moves.begin(); it != moves.end(); it++, moveNumber++)
	{
		Move* move = (*it);
		if (move->getWho() == MOVE_QUEEN)
			board->moveQueen(move->getToX(), move->getToY());
		else
			board->moveBishop(move->getToX(), move->getToY());
		stream << "Move number:	" << moveNumber << endl;
		move->write(stream);
		stream << endl;
		board->writeBoard(stream);
	}
}

/**
 * print best solution
 */
void Solver::printSolution()
{
	if (bestSolution == NULL)
	{
		cout << "ERROR: No solution found!" << endl;
		return;
	}

	cout << "----------------" << endl
		 << "  BEST SOLUTION " << endl
		 << "----------------" << endl;

	list<Move*> moves = bestSolution->getMoves();

	cout << "# of moves:	" << moves.size() << endl << endl;
	cout << "Initial state" << endl << endl;

	board->printBoard();

	int moveNumber = 1;
	for (list<Move*>::iterator it = moves.begin(); it != moves.end(); it++, moveNumber++)
	{
		Move* move = (*it);
		if (move->getWho() == MOVE_QUEEN)
			board->moveQueen(move->getToX(), move->getToY());
		else
			board->moveBishop(move->getToX(), move->getToY());
		cout << "Move number:	" << moveNumber << endl;
		move->print();
		cout << endl;
		board->printBoard();
	}
}
